跳到主要内容

Berkeley CS188 学习笔记（1）

· 阅读需 7 分钟

注，本文系从 https://web.archive.org 抢救而恢复，可能会丢失一些信息。

UCB 的 CS188 课程名为 Introduce to AI，人工智能导论，在 edX 网站中可以进行在线学习，链接：CS188

本文主要是对 Lecture2&3 做一个总结，这两次课着重介绍了对搜索问题的建模方法以及搜索方法。

Search Problem​

一个搜索问题由几个部分组成：状态空间（state space）、继承函数（successor function）、开始状态（start state）以及结束测试（goal test）。解决方案则是由一系列动作（action）组成，这些动作可以使开始状态变化至结束状态。

举个例子，先来看这个地图：

Imgur

对于一个旅游问题，比如某人想从城市 Arad 移动至城市 Bucharest 来说，以上提到的几个要素的建模方法如下：

  • 状态空间：地图中所有城市；
  • 继承函数：假设旅行者现在所在的城市为 TT，则继承函数为 S(T)=S(T)= 所有与 TT 邻接的城市；
  • 开始状态：城市 Arad；
  • 结束测试：旅行者是否身处于城市 Bucharest。

进而，对于搜索问题，我们可以构建一个状态空间图，其中每个状态至多只在图中出现一次，继承关系可以用有向边来表示。但对很多问题来说，把整个图存放在内存中是一件几乎不可能的事情（太大），所以转而考虑构建状态空间树，从而进行搜索。

先来看一下搜索算法的框架：

Imgur

接下来的三种搜索方法都是以上面这个框架为基础。在该算法框架中，closed 是一个 set，以保证已经扩展过的状态不会再次被遍历到；fringe 则是一个容器，用来存储搜索中遍历到的状态；而 strategy 则是会影响容器 fringe 的排列方式。

如果说刚刚介绍的那套算法流程看起来比较陌生的话，那么深度优先搜索和广度优先搜索我们就比较熟悉了。对于DFS（Depth First Search）来讲，fringe 和 strategy 所组成的数据结构就是栈，而对BFS（Breadth First Search）来说，其对应的数据结构则是队列。在 Uninformed Search 中，还有一种搜索方法 UCS（Uniform Cost Search），这种方法与 Dijkstra 算法比较相似，只不过是在这个算法框架内缺少了 relax 操作，也即 UCS 比 Dijkstra 算法略逊一筹。对 Dijkstra 算法比较熟悉的同学可以看出，优先级队列是在这套算法框架中需要使用的数据结构。

这三种搜索方法的一些性质可以罗列如下：

  • DFS
    • 扩张节点个数复杂度
      • O(bm)O(b^{m})，mm 为搜索树的高度，bb 为树中所有节点的最大子节点数
    • 空间复杂度
      • O(bm)O(bm)
    • 能否搜索到任意一个解？
      • 如果 mm 有限，则可以
    • 搜索到的解是否最优？
      • 不一定
  • BFS
    • 扩张节点个数复杂度
      • O(bs)O(b^{s})，ss 为最浅解在树中的搜索深度
    • 空间复杂度
      • O(bs)O(b^{s})
    • 能否搜索到任意一个解？
      • 可以
    • 搜索到的解是否最优？
      • 除非 cost 均为固定常数，否则不一定
  • UCS
    • 扩张节点个数复杂度
      • O(bC∗/ϵ)O(b^{C^{*}/\epsilon})，C∗C^{*} 为最优解的cost，ϵ\epsilon 为边的最小cost
    • 空间复杂度
      • O(bC∗/ϵ)O(b^{C^{*}/\epsilon})
    • 能否搜索到任意一个解？
      • 如果 C∗C^{*} 有限且 ϵ\epsilon 为正数，就可以
    • 搜索到的解是否最优？
      • 可以

之前所介绍的搜索方法完全没有考虑当前搜索到的状态与最终解的状态之间的距离，比如说某人想去东边的一座城市，在搜索时可能会将西方的城市也进行扩张搜索，然而这是完全没有意义的，这是南辕北辙。所以我们需要人为引入启发式函数来引导搜索方向。

一个启发式函数对当前状态与解状态之间的距离进行估计，具体函数的表达需要每个人自己去估计，比如在寻路问题中可以利用曼哈顿距离、欧氏距离等等。

在A*（A-star）算法中，将边的 cost 与启发式函数相加，得到函数 f=g+hf=g+h。使用 ff 作为优先级队列的key，就能够使用上一节所介绍的搜索算法框架来实现 A* 算法。

为保证 A* 算法的最优性，启发式函数 hh 需要满足性质：启发式函数所估计出的 cost≤ 实际 cost，用数学表达出来即，

0≤h(n)≤h∗(n)0\le h(n)\le h^{*}(n)

其中 h∗h^{*} 是从当前状态到最近解状态的真实 cost。（admissible）以及，

h(A)−h(C)≤cost(A→C)h(A)-h(C)\le cost(A\rightarrow C)

（consistency）

A* 算法将会在扩张更少节点的情况下搜索到最优解，在Pacman游戏中的寻路问题上，A* 算法与贪心法、UCS 的比较如下图：

Imgur

可以看到，贪心法虽然扩张的节点较少，但并没有找到最优解；UCS 虽然找到了最优解，但几乎搜索了整张地图；而 A* 算法在找到了最优解的情况下，只搜索了大概半张地图。